// NC15 求二叉树的层序遍历
// https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3 deque
// 避免层级记录
// 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
// 给定的二叉树是{3,9,20,#,#,15,7},
// 该二叉树层序遍历的结果是
// [
// [3],
// [9,20],
// [15,7]
// ]

vector<vector<int> > levelOrder(TreeNode* root) {
  // write code here
  vector<vector<int> > res;
  if (root == nullptr) {
    return res;
  }
  deque<TreeNode*> deqNode;
  deqNode.push_back(root);

  for (int level = 0; !deqNode.empty(); level++) {
    vector<int> vtTemp;
    for (int i = deqNode.size(); i > 0; i--) {
      TreeNode* node = deqNode.front();
      deqNode.pop_front();
      vtTemp.push_back(node->val);
      if (node->left) deqNode.push_back(node->left);
      if (node->right) deqNode.push_back(node->right);
    }
    res.push_back(vtTemp);
  }
  return res;
}
